// Programs for reversing bits.
// Max line length is 57, to fit in hacker.book.
#include <stdio.h>
#include <stdlib.h>     // To define "exit", req'd by XLC.

// Rotate shift left.
unsigned shlr(unsigned x, int n) {
   return (x << n) | (x >> (32 - n));
}

// Reversing bits in a word, basic interchange scheme.
unsigned rev1(unsigned x) {
   x = (x & 0x55555555) <<  1 | (x & 0xAAAAAAAA) >>  1;
   x = (x & 0x33333333) <<  2 | (x & 0xCCCCCCCC) >>  2;
   x = (x & 0x0F0F0F0F) <<  4 | (x & 0xF0F0F0F0) >>  4;
   x = (x & 0x00FF00FF) <<  8 | (x & 0xFF00FF00) >>  8;
   x = (x & 0x0000FFFF) << 16 | (x & 0xFFFF0000) >> 16;
   return x;
}

// Reversing bits in a word, refined basic scheme.
// 24 operations + 6 for loading constants = 30 insns.
// This is Figure 7-1 in HD.
unsigned rev2(unsigned x) {
   x = (x & 0x55555555) <<  1 | (x >>  1) & 0x55555555;
   x = (x & 0x33333333) <<  2 | (x >>  2) & 0x33333333;
   x = (x & 0x0F0F0F0F) <<  4 | (x >>  4) & 0x0F0F0F0F;
   x = (x << 24) | ((x & 0xFF00) << 8) |
       ((x >> 8) & 0xFF00) | (x >> 24);
   return x;
}

// Reversing the rightmost 6 bits in a word.
unsigned rev3(unsigned x) {
   return (x*0x00082082 & 0x01122408) % 255;
}

// Reversing the rightmost 6 bits in a word.
unsigned rev4(unsigned x) {
   unsigned t;
   t = x*0x00082082 & 0x01122408;
   return (t*0x01010101) >> 24;
}

// Reversing the rightmost 8 bits in a word.
// Problem: can't change divide by 1023 to a 32x32 ==> 32 multiply.
unsigned rev5(unsigned x) {
   unsigned s, t;
   s = x*0x02020202 & 0x84422010;
   t = x*8 & 0x00000420;
   return (s + t) % 1023;
}

// Reversing the rightmost 8 bits in a word.
unsigned rev6(unsigned x) {
   unsigned s, t;
   s = x*0x00020202 & 0x00422010;
   t = x*0x00008008 & 0x00210420;
   return (s + t) % 1023;
}

// Reversing the rightmost 8 bits in a word.
unsigned rev7(unsigned x) {
   unsigned s, t;

   s = x*0x00020202 & 0x01044010;
   t = x*0x00080808 & 0x02088020;
   return (s + t) % 4095;
}

// Reversing the rightmost 8 bits in a word.
// Same as above but made more efficient, 15 Brisc ops.
unsigned rev8(unsigned x) {
   unsigned u, m, s, t;

   u = x*0x00020202;
   m = 0x01044010;
   s = u & m;
   t = (u << 2) & (m << 1);
   return 0x01001001*(s + t) >> 24;
// return (s + t) % 4095;       // Alternative, equivalent to above.
}

// Reversing the rightmost 9 bits in a word.
// Can't change the remainder to a multiply.
unsigned rev9(unsigned x) {
   unsigned s, t;

   s = x*0x01001001 & 0x84108010;
// t = x*0x00040040 & 0x00841080;
   t = ((x*0x01001001) >> 6) & (0x84108010 >> 8);  // Alternative,
                                // better after commoning.
   return (s + t) % 1023;
}

// Reversing the rightmost 9 bits in a word.
// Can't change the remainder to a multiply.
// Probably rev9 is a little better --- smaller numbers.
unsigned rev10(unsigned x) {
   unsigned s, t;

   s = x*0x40100401 & 0x84108010;
   t = x*0x04010040 & 0x21042000;
   return (s + t) % 4095;
}

// Same as above but made more efficient.
unsigned rev10a(unsigned x) {
   unsigned u, m, s, t;

   u = x*0x40100401;
   m = 0x84108010;
   s = u & m;
   t = (u << 6) & (m >> 2);
   return (s + t) % 4095;
}

/* The following routines are new (not in HD first edition).

   Reversing bits in a word using rotate shifts and the "and not"
instruction. 17 operations (25 full RISC instructions).
15 cycles on a machine with sufficient parallelism.
   Don't know why I didn't put this in HD. Maybe next time. */

unsigned rev11(unsigned x) {
   x = shlr(x & 0x00FF00FF, 16) | x & ~0x00FF00FF;
   x = shlr(x & 0x0F0F0F0F,  8) | x & ~0x0F0F0F0F;
   x = shlr(x & 0x33333333,  4) | x & ~0x33333333;
   x = shlr(x & 0x55555555,  2) | x & ~0x55555555;
   x = shlr(x, 1);
   return x;
}

/* Reversing bits in a word, similar to above but doesn't require "and
not." Uses XOR instead. By Vesa Karvonen, found in The Assembly Gems
Page, http://www.df.lth.se/~john_e/fr_gems.html.
   17 operations (25 full RISC instructions).
15 cycles on a machine with sufficient parallelism.
   Uses the identity

   x & ~m = (x & m) ^ x

to change

   x = shlr(x & 0x00FF00FF, 16) | x & ~0x00FF00FF;

to the first executable line in the function below.
   This is new to me, not in Hacker's Delight. */

unsigned rev11a(unsigned x) {
   unsigned t;
   t = x & 0x00FF00FF; x = shlr(t, 16) | (t ^ x);
   t = x & 0x0F0F0F0F; x = shlr(t,  8) | (t ^ x);
   t = x & 0x33333333; x = shlr(t,  4) | (t ^ x);
   t = x & 0x55555555; x = shlr(t,  2) | (t ^ x);
   x = shlr(x, 1);
   return x;
}

/* The next routine, by Donald E. Knuth, reverses a 32-bit word in only
four steps. It uses "ternary" swapping of some fields, and a rotate
shift for one step (nice, especially if you have that instruction,
because it doesn't need masks). It operates as follows (c.f. a note
from DEK):

   0123456789abcdefghijklmnopqrstuv (given)
   fghijklmnopqrstuv0123456789abcde (cyclic shift 15)
   pqrstuvmnofghijklabcde5678901234 (10-swap)
   tuvspqrmnojklifghebcda9678541230 (4-swap)
   vutsrqpomnlkjihgfedcba9876543210 (2-swap)

If you have the rotate shift, this is 22 operations, or 34 instructions,
counting loading the six distinct masks. Beats rev2 by 2 operations
or 2 instructions. But it doesn't beat rev11a (17 ops, 25 insns). */

unsigned rev12(unsigned x) {
   x = shlr(x, 15);             // Cyclic shift 15.
   x = (x & 0x003F801F) << 10 | (x & 0x01C003E0) | (x >> 10) & 0x003F801F;
   x = (x & 0x0E038421) <<  4 | (x & 0x11C439CE) | (x >>  4) & 0x0E038421;
   x = (x & 0x22488842) <<  2 | (x & 0x549556B5) | (x >>  2) & 0x22488842;
   return x;
}

/* Next is a variation of rev12 that replaces assignments of the form

   x = (x & M1) << s | (x & M2) | (x >> s) & M1;

where M2 is ~(M1 | (M1 << s)), with:

   t = (x ^ (x >> s)) & M1; x = (t | (t << s)) ^ x;

which saves one operation (three instructions) on each of the ternary
swap steps. Thus, it takes 19 operations or 25 instructions. */

unsigned rev12a(unsigned x) {
   unsigned t;

   x = shlr(x, 15);             // Cyclic shift 15.
   t = (x ^ (x >> 10)) & 0x003F801F; x = (t | (t << 10)) ^ x;
   t = (x ^ (x >>  4)) & 0x0E038421; x = (t | (t <<  4)) ^ x;
   t = (x ^ (x >>  2)) & 0x22488842; x = (t | (t <<  2)) ^ x;
   return x;
}

/* The next routine reverses the rightmost 16 bits of a word, assuming
the leftmost 16 bits are clear at the start. It is an old algorithm by
Christopher Strachey.
   The way it works is to build up the reversed halfword in the left
half of the register x. It does this by noting how many positions each
bit must move to the left, to be placed in its proper position in the
left half of the word. Then, each bit that must move 16 or more
positions is moved left 16. Then each bit that must move 8 or more
positions (after the first move of 16 positions) is moved left 8. Then
4, then 2, then 1. Lastly a shift left of 1 is required to put the
result in the left half of the register (as in Strachey), or a shift
right of 17 is done to put the result in the rightmost 16 bits (as is
done here).
   Here is how far to the left the bits in postions 0 to 15 must move:
   31 30 ... 17 16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0
                    1  3  5  7  9 11 13 15 17 19 21 23 25 27 29 31

  Let the word initially be 0000 0000 0000 0000 abcd efgh ijkl mnop
  Then after shift of 16:   0000 0000 ijkl mnop abcd efgh ijkl mnop
       After shift of 8:    0000 mnop ijkl efgh abcd mnop ijkl mnop
       After shift of 4:    00op mnkl ijgh efcd abop mnkl ijop mnop
       After shift of 2:    0pon mlkj ihgf edcb apon mlkj ipon mpop
       After right sh. 15:  0000 0000 0000 0000 ponm lkji hgfe dcba

16 operations.
 */

unsigned rev13(unsigned x) {
   x = x | ((x & 0x000000FF) << 16);
   x = (x & 0xF0F0F0F0) | ((x & 0x0F0F0F0F) << 8);
   x = (x & 0xCCCCCCCC) | ((x & 0x33333333) << 4);
   x = (x & 0xAAAAAAAA) | ((x & 0x55555555) << 2);
   x = x >> 15;
   return x;
}

int errors;
void error(int x, int y) {
   errors = errors + 1;
   printf("Error for x = %08x, got %08x\n", x, y);
}

int main() {
   int i, n;
   unsigned r;
   static unsigned test[] = {0,0, 1,0x80000000, 2,0x40000000,
      3,0xC0000000, 4,0x20000000, 5,0xA0000000, 6,0x60000000,
      7,0xE0000000, 8,0x10000000, 9,0x90000000, 10,0x50000000,
      11,0xD0000000, 12,0x30000000, 13,0xB0000000, 14,0x70000000,
      15,0xF0000000, 16,0x08000000, 59,0xDC000000, 60,0x3C000000,
      61,0xBC000000, 62,0x7C000000, 63,0xFC000000, 64,0x02000000,
      125,0xBE000000, 126,0x7E000000, 127,0xFE000000, 128,0x01000000,
      253,0xBF000000, 254,0x7F000000, 255,0xFF000000, 256,0x00800000,
      257,0x80800000,
      509,0xBF800000, 510,0x7F800000, 511,0xFF800000, 512,0x00400000,
      0x55555555,0xAAAAAAAA,
      0x01234567,0xE6A2C480, 0xFFFFFFF1,0x8FFFFFFF, 0xFFFFFFFF,0xFFFFFFFF};

   n = sizeof(test)/4;

   printf("rev1:\n");
   for (i = 0; i < n; i += 2) {
      r = rev1(test[i]);
      if (r != test[i+1]) error(test[i], r);
      r = rev1(test[i+1]);
      if (r != test[i]) error(test[i+1], r);}

   printf("rev2:\n");
   for (i = 0; i < n; i += 2) {
      r = rev2(test[i]);
      if (r != test[i+1]) error(test[i], r);
      r = rev2(test[i+1]);
      if (r != test[i]) error(test[i+1], r);}

   printf("rev3:\n");
   for (i = 0; i < n; i += 2) {
      r = rev3(test[i] & 0x0000003F);
      if (r != test[i+1] >> 26) error(test[i], r);
      r = rev3(test[i+1] & 0x0000003F);
      if (r != test[i] >> 26) error(test[i+1], r);}

   printf("rev4:\n");
   for (i = 0; i < n; i += 2) {
      r = rev4(test[i] & 0x0000003F);
      if (r != test[i+1] >> 26) error(test[i], r);
      r = rev4(test[i+1] & 0x0000003F);
      if (r != test[i] >> 26) error(test[i+1], r);}

   printf("rev5:\n");
   for (i = 0; i < n; i += 2) {
      r = rev5(test[i] & 0x000000FF);
      if (r != test[i+1] >> 24) error(test[i], r);
      r = rev5(test[i+1] & 0x000000FF);
      if (r != test[i] >> 24) error(test[i+1], r);}

   printf("rev6:\n");
   for (i = 0; i < n; i += 2) {
      r = rev6(test[i] & 0x000000FF);
      if (r != test[i+1] >> 24) error(test[i], r);
      r = rev6(test[i+1] & 0x000000FF);
      if (r != test[i] >> 24) error(test[i+1], r);}

   printf("rev7:\n");
   for (i = 0; i < n; i += 2) {
      r = rev7(test[i] & 0x000000FF);
      if (r != test[i+1] >> 24) error(test[i], r);
      r = rev7(test[i+1] & 0x000000FF);
      if (r != test[i] >> 24) error(test[i+1], r);}

   printf("rev8:\n");
   for (i = 0; i < n; i += 2) {
      r = rev8(test[i] & 0x000000FF);
      if (r != test[i+1] >> 24) error(test[i], r);
      r = rev8(test[i+1] & 0x000000FF);
      if (r != test[i] >> 24) error(test[i+1], r);}

   printf("rev9:\n");
   for (i = 0; i < n; i += 2) {
      r = rev9(test[i] & 0x000001FF);
      if (r != test[i+1] >> 23) error(test[i], r);
      r = rev9(test[i+1] & 0x000001FF);
      if (r != test[i] >> 23) error(test[i+1], r);}

   printf("rev10:\n");
   for (i = 0; i < n; i += 2) {
      r = rev10(test[i] & 0x000001FF);
      if (r != test[i+1] >> 23) error(test[i], r);
      r = rev10(test[i+1] & 0x000001FF);
      if (r != test[i] >> 23) error(test[i+1], r);}

   printf("rev10a:\n");
   for (i = 0; i < n; i += 2) {
      r = rev10a(test[i] & 0x000001FF);
      if (r != test[i+1] >> 23) error(test[i], r);
      r = rev10a(test[i+1] & 0x000001FF);
      if (r != test[i] >> 23) error(test[i+1], r);}

   printf("rev11:\n");
   for (i = 0; i < n; i += 2) {
      r = rev11(test[i]);
      if (r != test[i+1]) error(test[i], r);
      r = rev11(test[i+1]);
      if (r != test[i]) error(test[i+1], r);}

   printf("rev11a:\n");
   for (i = 0; i < n; i += 2) {
      r = rev11a(test[i]);
      if (r != test[i+1]) error(test[i], r);
      r = rev11a(test[i+1]);
      if (r != test[i]) error(test[i+1], r);}

   printf("rev12:\n");
   for (i = 0; i < n; i += 2) {
      r = rev12(test[i]);
      if (r != test[i+1]) error(test[i], r);
      r = rev12(test[i+1]);
      if (r != test[i]) error(test[i+1], r);}

   printf("rev12a:\n");
   for (i = 0; i < n; i += 2) {
      r = rev12a(test[i]);
      if (r != test[i+1]) error(test[i], r);
      r = rev12a(test[i+1]);
      if (r != test[i]) error(test[i+1], r);}

   printf("rev13:\n");
   for (i = 0; i < n; i += 2) {
      r = rev13(test[i] & 0x0000FFFF);
      if (r != test[i+1] >> 16) error(test[i], r);
      r = rev13(test[i+1] & 0x0000FFFF);
      if (r != test[i] >> 16) error(test[i+1], r);}

   if (errors == 0)
      printf("Passed all %d cases.\n", sizeof(test)/8);
}
